﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms.Implementation.ComparisonSorts
{
    public class MergeSort : Algorithm
    {
        protected override void ExecuteAlgorithm(int indexStart, int indexEnd)
        {
            if (indexStart < indexEnd)
            {
                int indexMiddle = indexStart + (indexEnd - indexStart) / 2;

                ExecuteAlgorithm(indexStart, indexMiddle);
                ExecuteAlgorithm(indexMiddle + 1, indexEnd);

                Merge(indexStart, indexMiddle, indexEnd);
            }
        }

        private void Merge(int indexStart, int indexMiddle, int indexEnd)
        {
            int leftLength = indexMiddle - indexStart + 1;
            int rightLength = indexEnd - indexMiddle;

            int[] leftArray = new int[leftLength];
            int[] rightArray = new int[rightLength];

            for (int i = 0; i < leftLength; i++)
            {
                leftArray[i] = _sampleData[indexStart + i];
            }

            for (int i = 0; i < rightLength; i++)
            {
                rightArray[i] = _sampleData[indexMiddle + 1 + i];
            }

            int m = 0;
            int n = 0;

            for (int i = 0; i < leftLength + rightLength; i++)
            {
                if (m == leftLength && n < rightLength)
                {
                    _sampleData[indexStart + i] = rightArray[n];
                    n++;
                }
                else if (m < leftLength && n == rightLength)
                {
                    _sampleData[indexStart + i] = leftArray[m];
                    m++;
                }
                else
                {
                    if (leftArray[m] <= rightArray[n])
                    {
                        _sampleData[indexStart + i] = leftArray[m];
                        m++;
                    }
                    else
                    {
                        _sampleData[indexStart + i] = rightArray[n];
                        n++;
                    }
                }
            }
        }
    }
}
